小小算法，频繁刺激-Palindrome Number

发表于 | 分类于 | 阅读次数:

今天刷LeetCode，遇到一道简单算法题，Palindrome Number，但解题过程比较有意思，借此文记录下。

解析题目

问题描述： Determine whether an integer is a palindrome. Do this without extra space. 判断一个int类型的数是否为回文数？ 不使用额外空间。

关于什么是回文数？给个定义：正反方向输出的值相等的数称为回文数。 没理解到的，可以去网上搜下。

举例：1、1221、11211等是回文数；-1、0、12、123323等就不是回文数。

那什么是回文字符串呢？可以参考这篇文章【算法】Longest Palindromic Substring。

分析思路

理解题目后，总共想到三个思路：

  • 按位比较： 1. 计算整数的位数（长度）， 2. 从第一位和最后一位开始依次递增和增减循环比较。
  • 反转输入int，与原数比较看是否相等。 之前有道题是：反转一个int数，其中需要考虑溢出问题。
  • 转成字符串，按位比较。 但题目限制不能占用额外内存。

考虑使用第一种思路，这道题比较简单，有了思路后，按说就可以编码了，但为了养成好习惯，别着急编码还是想下case情况先。我只想到两个：1.负数不是回文数。 2. 考虑位数奇偶数情况。虽然少，过程不能省。

开始编码，贴下我第一版代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public boolean isPalindrome(int x) {
        if (x < 0) { // 负数情况
            return false;
        }
        final int originX = x;
        int bitCount = 1;
        // 算出有多少位（长度）
        while (x >= 10) {
            x /= 10;
            bitCount++;
        }
        int l = 0;
        int r = bitCount - 1;
        // 依次比较
        while (getBitNum(originX, bitCount, l) == getBitNum(originX, bitCount, r)) {
            l++;
            r--;
            if (l >= r) {
                return true;
            }
        }
        return false;
    }
	// 去取原数对应位下标的数值
    int getBitNum(int num, final int len, int index) {
        int temp = 1;
        while (len - index > 1) {
            temp *= 10;
            index++;
        }
        return (num / temp) % 10;
    }

LeetCode上类似白板编程，代码比较龊，请见谅。编写完了自测case，好都没问题，这么简单那就提交吧，提交是通过了，但提示该算法击败了1.7%的其它用户提交，也就是说效率很差，垫底了。这样怎么行呢，毕竟咋还是有追求的程序猿对吧。于是分析代码，其中三处循环，还有嵌套；估算时间复杂度为：O(n*log10n)。 （ps:时间复杂度计算，不是很清楚，有知道的大神请留言指教，谢谢。）

怀着焦虑的心情，点开了官方推荐解法页面。看到一半，哎呀，这不是上文中我想到的第二条思路吗，反转int整数。但官方建议只反转int的一半，然后与剩下一半比较，如果相等则是回文数。这就完美避开了Integer.MAX_VALUE溢出问题，不得不服。

想着先不看其代码实现，自己写一下再说，于是在之前基础上改出了下面的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
boolean isPalindromeNum(int x) {
        if (x < 0) {
            return false;
        }
        final int originX = x;
        int bitCount = 1;
        while (x >= 10) {
            x /= 10;
            bitCount++;
        }
        int index = 0;
        int halfNum = 0;
        final int halfLen = bitCount / 2;
        int tempX = originX;
        while (index < halfLen) {
            halfNum = halfNum * 10 + tempX % 10;
            tempX /= 10;
            index++;
        }
        // 判断奇偶情况
        return halfNum == (bitCount % 2 == 0 ? tempX : tempX / 10);

提交跑起来，嗯快了不少，击败了48%，感觉不错对吧。这会去看官方给出的C#代码实现，看完感觉受到一万点伤害，吐血了。不说了，贴代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
boolean isPalindromeNumOfficial(int x) {
    // Special cases:
    // As discussed above, when x < 0, x is not a palindrome.
    // Also if the last digit of the number is 0, in order to be a palindrome,
    // the first digit of the number also needs to be 0.
    // Only 0 satisfy this property.
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    int revertedNumber = 0;
    while (x > revertedNumber) {
        revertedNumber = revertedNumber * 10 + x % 10;
        x /= 10;
    }
    // When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
    // For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,
    // since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
    return x == revertedNumber || x == revertedNumber / 10;
}

注释写的很清楚了，主要有三点：1. 判断尾数为0的情况 2. 取消判断位数的逻辑 3. 聪明处理奇偶位数情况。
解析下第一点：比如 10 的倍数的数 10010，它也会返回 true，所以要排除非零情况10的倍数。

小结

小小一道简单的算法题，都能频繁带给你刺激，是不是很过瘾。想想平时我们写的代码，是不是应该翻出来再斟酌斟酌，哈哈哈。

最后贴下转字符串思路实现的代码。

1
2
3
4
5
6
7
8
9
10
11
12
// 转字符串在比较 ，速度是很快的
    public boolean isPalindromeForString(int x) {
        String num = String.valueOf(x);
        if (num == null || num.length() == 0) return true;
        int start = 0, end = num.length() - 1;
        while (start < end) {
            if ((char) num.charAt(start) != (char) num.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }

以上代码均由Java实现，项目地址https://github.com/yangjiantao/DSAA。

0%